﻿using SearchAlgorithms.Interfaces;
using System;
using System.Collections.Generic;

namespace SearchAlgorithms.Algorithms.Search
{
    public class KMPSearch : ISearchAlgorithm
    {
        //属性的初始化
        public static KMPSearch Default { get; } = new KMPSearch();

        private KMPSearch()
        {
        }

        //next数组
        public void ComputeLPSArray<T>(IReadOnlyList<T> patterns, int[] lps) where T : IEquatable<T>
        {
            int length = 0;
            int i = 1;
            lps[0] = 0;
            while (i < patterns.Count)
            {
                if (patterns[i].Equals(patterns[length]))
                {
                    length++;
                    lps[i] = length;
                    i++;
                }
                else
                {
                    length = length == 0 ? 0 : lps[length - 1];
                    i++;
                }
            }
        }



        public int SingleSearch<T>(IReadOnlyList<T> input, IReadOnlyList<T> search, int start, int count)
            where T : IEquatable<T>
        {
            int[] lps = new int[search.Count];
            int j = 0;

            ComputeLPSArray(search, lps);

            int i = start;
            while (i < input.Count)
            {
                if (search[j].Equals(input[i]))
                {
                    j++;
                    i++;
                }
                if (j == search.Count)
                {

                    return i - j;

                }

                else if (i < input.Count && !search[j].Equals(input[i]))
                {

                    if (j != 0)
                        j = lps[j - 1];
                    else
                        i++;
                }
            }

            return -1;
        }

        public int SingleSearch<T>(Span<T> input, ReadOnlySpan<T> search, int start, int count)
           where T : IEquatable<T>
        {
            int[] lps = new int[search.Length];
            int j = 0;

            ComputeLPSArray(search.ToArray(), lps);

            int i = start;
            while (i < input.Length)
            {
                if (search[j].Equals(input[i]))
                {
                    j++;
                    i++;
                }
                if (j == search.Length)
                {
                    return i - j;
                }

                else if (i < input.Length && !search[j].Equals(input[i]))
                {

                    if (j != 0)
                        j = lps[j - 1];
                    else
                        i++;
                }
            }

            return -1;
        }
    }
}


